package base_Suanfa.dongtaiguihua;
//{6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。
public class lianxuzichuanhe {
    // 使用动态规划法实现
    public int findGreatestSunOfSubArray(int[] array){
        if(array.length == 0){
            return 0;
        }

        // 记录当前子数组中的最大值
        int res = array[0];
        // 包含array[i]的连续数组的最大值
        int max = array[0];

        for (int i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i]);
            res = Math.max(max, res);
        }
        return res;
    }

    // 测试
    public static void main(String[] args) {
        lianxuzichuanhe find = new lianxuzichuanhe();
        int[] array = {-1,-2,-3,-10,-4,-7,2,-5};
        int maxSumOfSubArray = find.findGreatestSunOfSubArray(array);
        System.out.println(maxSumOfSubArray);
    }

}
